Thirty Days of Metal — Day 27: Tessellation

Warren Moore

·

Follow

12 min read

·

Jun 2, 2022

98

This series of posts is my attempt to present the Metal graphics programming framework in small, bite-sized chunks for Swift app developers who haven’t done GPU programming before.

If you want to work through this series in order, start here. To download the sample code for this article, go here.

Last time, we looked at how to add the illusion of finer surface detail by using a normal map to vary the lighting normal at a higher rate than the underlying vertex normals.

This time, we will look at tessellation, a technique for generating more geometry dynamically without needing to allocate more vertex storage. Tessellation works by subdividing the primitives in a mesh in a systematic way, producing additional, smaller triangles.

To perform tessellation, we will issue draw calls for a new kind of primitive: patches. A patch is a quadrilateral (“quad”) or triangular coordinate space combined with a set of control points, which influence how the subdivided geometry is positioned. We will call the patch coordinate space a “domain.”

Quad and triangle domains are parameterized differently. Positions in a quad patch have two parameters, commonly labeled u and v, similar to how we denote texture coordinates. Triangle domains have three coordinates, labeled u, v, and w. These are barycentric coordinates, meaning they express how much influence each vertex of the domain has on the position. Points inside such a patch have coordinates that sum to 1.

These two different coordinate schemes are illustrated below with example positions.

Rather than vertices, patches have control points. Like vertices, control points have associated attributes. Unlike vertices, multiple control points are fetched at once in the vertex function. We are responsible for writing a function that interprets the control point data according to our chosen subdivision scheme. Furthermore, the number of control points is not necessarily equal to the number of vertices commonly associated with the patch domain. Patches can have between 0 and 32 control points.

Patches differ from ordinary mesh geometry in that they are not processed by the regular vertex pipeline. Instead, they are subdivided before the vertex shader runs, according to a fixed-function stage called the tessellator. The tessellator operates by fetching the tessellation factors for a patch, subdividing the patch, and passing the resulting vertices to the vertex shader.

The modified graphics pipeline is illustrated below. An optional compute function may be used to populate the tessellation factor buffer. The tessellation factors are consumed by the fixed-function tessellator, which subdivides the patch domain accordingly. Then, the subdivided geometry passes to the post-tessellation vertex stage. We will discuss all of these steps in greater detail below.

Tessellation Factors

Recall from our previous discussion of primitives that Metal cannot render quadrilaterals; they must be triangulated first. Since tessellation is a fixed-function stage, we have limited control over how the subdivision of patches occurs. The two most important inputs to the tessellator are the tessellation factors and the partition mode.

Tessellation factors are numbers that determine how many times each region of the tessellation domain should be subdivided. A quad domain has a total of six factors: four edge factors and two inside factors. Edge factors determine how many times each edge should be subdivided, while inside factors determine how many times the interior region should be subdivided. Triangular tessellation factors are similar, except there are three edge factors (corresponding to the three edges of the triangle) and only one inside factor, corresponding to the interior region. These various factors are illustrated below.

Why two different kinds of factors? One reason is that if adjacent patches have different edge factors, or if the vertex function produces different positions for vertices that are supposed to be coincident, cracks will appear. If we can control the subdivision of the interior of the patch separately from its edges, we can potentially use a lower factor inside and whatever factor is needed to avoid cracking along the edges, allowing us to allocate vertices where they are needed most.

The partition mode determines subtler aspects of how the subdivided vertices are distributed. This is discussed below in the implementation section.

Authoring Meshes for Tessellation

A 3D artist must choose which patch type to use when designing a mesh. Different subdivision types are suitable for different uses. Quad patches are commonly used with subdivision schemes like Catmull-Clark subdivision surfaces. Triangle patches can be used with other schemes like Loop subdivision and PN triangles.

Generating additional geometry is not very useful by itself: lighting and texturing are commonly done per-pixel, so without the addition of other information, more vertices just mean more work for the GPU. The power of tessellation comes from the fact that we can supply additional information in the form of textures and control point attributes. Most 3D modeling packages support exporting various per-control point attributes such as normals, tangents, and texture coordinates.

It is important to maintain the topology of the model through all stages from authoring to rendering. Asset import libraries sometimes prefer to triangulate input meshes so that they are compatible with real-time renderers, but triangulating a quad patch destroys the information needed to render the mesh correctly with tessellation. We will see below how to use Model I/O to import patch geometry without disrupting the authored topology.

A Patch Mesh Class

Since we will be drawing patches rather than triangles, we need a slightly different data model for our submeshes. Specifically, rather than a primitive type, our submesh will have a patch type and a control point count. It will also have a patch count derived from the index count and control point count.

The PatchSubmesh interface looks like this:

enum PatchType {
    case tri
    case quad
}class PatchSubmesh {
    let patchType: PatchType
    let patchControlPointCount: Int
    let patchCount: Int
    let indexBuffer: MeshBuffer
    let indexType: MTLIndexType
    let indexCount: Int
    var material: Material?

Using this interface, we can easily draw each patch with a draw call.

Now that we know how to author and represent patch meshes, let’s look at how to actually use tessellation in Metal.

Tessellation in Metal

To perform tessellation in Metal, we have three tasks:

1. Write tessellation factors to a tessellation factor buffer.
2. Issue patch primitive draw calls.
3. Write a post-tessellation vertex function that transforms tessellated vertex positions and produces other interpolated vertex attributes.

Tessellation Factors

We can accomplish task #1 in a variety of ways depending on what we’re trying to do. In the simplest case, we can use a constant set of tessellation factors that apply to every patch. In other scenarios, we might want to take other information, such as the patch’s distance from the camera, into account to calculate tessellation factors for each patch. Updating factors can also be done at any rate we choose: we might write our tessellation factors once and reuse them across frames, or we might generate new tessellation factors every frame.

In the interest of keeping as much work as possible on the GPU, it is common to use compute functions to populate the tessellation factor buffer. Compute functions have the virtue of having direct access to GPU memory, and most algorithms we might use to determine tessellation factors can be implemented in a compute kernel for efficient parallel computation.

Tessellation factors in Metal are half-precision floating-point numbers; each factor occupies two bytes. Each patch type has a different tessellation factor structure, corresponding to the tessellation factor diagram above. The declarations of these structures in MSL are shown below.

struct MTLQuadTessellationFactorsHalf {
  half edgeTessellationFactor[4];
  half insideTessellationFactor[2];
};struct MTLTriangleTessellationFactorsHalf {
  half edgeTessellationFactor[3];
  half insideTessellationFactor;
};

The interpretation of these factors is dependent on the configuration of the render pipeline state, specifically the tessellation partition mode.

Here is a simplified definition of Metal’s MTLTessellationPartitionMode enumeration:

enum MTLTessellationPartitionMode {
    case pow2
    case integer
    case fractionalOdd
    case fractionalEven
}

The .pow2 mode is the most restrictive. The tessellation factors are rounded up to the nearest power of two, and the subdivided positions are evenly distributed along the relevant axis. In the .integer mode, the tessellation factors are rounded up to the nearest integer. For information on the other two partition modes, consult Apple’s documentation.

In the sample code, we somewhat arbitrarily choose the .integer partition mode:

renderPipelineDescriptor.tessellationPartitionMode = .integer

We also don’t bother computing tessellation factors dynamically; instead they are written into the constant buffer alongside the rest of the constant data.

Patch Draw Calls

To issue patch draw calls, we use one of the draw call methods on the render command encoder, just as we do when drawing ordinary meshes. There are indexed and non-indexed variants of these methods. We will focus here on the drawIndexedPatches(numberOfPatchControlPoints:patchStart:patchCount:patchIndexBuffer:patchIndexBufferOffset:controlPointIndexBuffer:controlPointIndexBufferOffset:instanceCount:baseInstance:) method. This method takes a lot of parameters, so let’s break it down.

The number of patch control points is the number of control points per patch. Recall that this is not necessarily the number of vertices in the corresponding primitive (3 for triangles and 4 for quads). Instead, each patch can have as many control points as are required to implement the desired subdivision scheme. By coincidence, the simple subdivision scheme we use in the sample code uses four control points per quad patch.

The patchStart and patchCount parameters determine the base patch index and number of patches to draw.

The patchIndexBuffer and its corresponding offset are used to specify a patch index buffer, which indicates the indices of the patches to render. This is distinct from the control point index buffer, which holds indices into the control point attribute buffers (much like an ordinary index buffer). These parameters are optional and we will set them to nil and 0 respectively.

The controlPointIndexBuffer and its corresponding offset specify the control point index buffer.

We will not perform instanced rendering, but the final two parameters allow us to specify the instance count and base instance index.

As with ordinary primitive rendering, we bind the mesh’s attribute buffers before issuing any draw calls. When tessellating, we additionally bind the tessellation factor buffer on the render command encoder:

renderCommandEncoder.setTessellationFactorBuffer(
  constantBuffer,
  offset: tessellationFactorOffset,
  instanceStride: 0)

(As mentioned above, for simplicity’s sake we just use the constant buffer to store the tessellation factors. In a real application this might be a dedicated buffer, and the factors might be computed dynamically.)

Using our PatchSubmesh class from above, we can now issue a patch draw call as follows:

let indexBuffer = submesh.indexBuffer                renderCommandEncoder.drawIndexedPatches(
  numberOfPatchControlPoints: submesh.patchControlPointCount,
  patchStart: 0,
  patchCount: submesh.patchCount,
  patchIndexBuffer: nil,
  patchIndexBufferOffset: 0,
  controlPointIndexBuffer: indexBuffer.buffer,
  controlPointIndexBufferOffset: indexBuffer.offset,
  instanceCount: 1,
  baseInstance: 0)

The Post-Tessellation Vertex Function

After the tessellator runs, we are responsible for figuring out where each vertex in the domain should be positioned in clip space, as well as calculating any other vertex attribute positions we might want interpolated, such as normals, tangents, and texture coordinates.

In this context, the vertex function is called a post-tessellation vertex function, because it runs after the tessellator. The vertex function operates on control points rather than on input vertices.

A post-tessellation vertex function must be preceded by a patch attribute that specifies the patch type and (optionally on iOS) the number of patch control points. It also takes a float2 parameter with the [[position_in_patch]] that Metal fills with the coordinates of the vertex in the patch domain. Here is a simplified function signature:

[[patch(quad, 4)]]
vertex VertexOut vertex_quad(
  patch_control_point<VertexIn> controlPoints [[stage_in]],
  float2 positionInPatch [[position_in_patch]])

The patch_control_point template takes a type parameter that defines the attributes of the control points. This type depends on what kind of data we need to generate interpolated vertices. In the simplest case, it can just be the same struct that we use to define our vertex attributes:

struct VertexIn {
  float3 position  [[attribute(0)]];
  float3 normal    [[attribute(1)]];
  float4 tangent   [[attribute(2)]];
  float2 texCoords [[attribute(3)]];
};

Since we are using the attribute attribute (confusing, I know), these values will be fetched in the same way that vertex data is ordinarily fetched when a vertex descriptor is provided during render pipeline state construction. However, we have to update our vertex descriptors to accommodate this. In particular, we need to set the step function to MTLVertexStepFunction.perPatchControlPoint rather than the default MTLVertexStepFunction.perVertex:

vertexDescriptor.layouts[0].stepFunction = .perPatchControlPoint

With this change, Metal will fetch control point data from our vertex buffers and populate the controlPointsparameter with all of the control point data for the surrounding patch each time the vertex function is called.

Notably, Model I/O does not have a distinct notion of patch primitives, so a MTLVertexDescriptor translated from an MDLVertexDescriptor needs to be fixed up by setting the step function when tessellation is being used.

Inside the vertex function itself, we are responsible for calculating whatever vertex properties we want from the control points. This is where we implement our chosen subdivision scheme.

A very helpful utility function for such calculations is bilerp, which performs bilinear interpolation among arbitrary values of a common type, such as float4. Bilerp can be implemented as follows:

template <typename T>
T bilerp(T c00, T c01, T c10, T c11, float2 uv) {
  T c0 = mix(c00, c01, T(uv[0]));
  T c1 = mix(c10, c11, T(uv[0]));
  return mix(c0, c1, T(uv[1]));
}

To use the bilerp function in the vertex function, we supply it with the control point attribute data we want to interpolate. In the simple case of interpolating just the position, the vertex function would look something like this:

[[patch(quad, 4)]]
vertex VertexOut vertex_simple_quad(
  patch_control_point<VertexIn> controlPoints [[stage_in]],
  float2 positionInPatch [[position_in_patch]])
{
  float3 p00 = controlPoints[0].position;
  float3 p01 = controlPoints[1].position;
  float3 p10 = controlPoints[3].position;
  float3 p11 = controlPoints[2].position;
  float3 position = bilerp(p00, p01, p10, p11, positionInPatch);  // ...
}

We read the position of each control point and pass them all into bilerp, along with the positionInPatchparameter, which tells us where in the patch we are. The bilerp function returns the model-space position of the interpolated vertex, which we can then process and transform in the ordinary ways.

Displacement Mapping

Now that we know how to write post-tessellation vertex functions, let’s put all of that subdivided geometry to work. We will implement a technique called displacement mapping, which uses a heightmap-like texture to displace, or move, vertices along the surface normal. This can produce intricate geometry that affects a shape’s silhouette in a way that naive normal mapping cannot.

To implement displacement mapping, we first need a displacement map. It will complement our existing base color and normal maps:

We first expand our Material type with an optional displacement texture member:

class Material {
    var baseColor = SIMD4<Float>(1, 1, 1, 1)
    var baseColorTexture: MTLTexture?
    var normalTexture: MTLTexture?
    var displacementTexture: MTLTexture?
}

Model I/O looks for an attribute named map_disp when loading MTL material files that accompany OBJ models, so we can use this directive to specify the displacement map:

map_Kd cobblestone_baseColor.png
map_tangentSpaceNormal cobblestone_normal.png
map_disp cobblestone_displacement.png

and later populate the displacement texture property during model loading:

if let displacementProperty = mdlMaterial.property(
  with: MDLMaterialSemantic.displacement) {
  if displacementProperty.type == .texture {
    if let textureURL = displacementProperty.urlValue {
      material.displacementTexture = 
        try? textureLoader.newTexture(URL: textureURL,
                                  options: textureOptions)
    }
  }
}

The post-tessellation vertex function needs the displacement map and the surface normal to perform displacement mapping, so we use our bilerp utility function to find the normal and other vertex properties:

[[patch(quad, 4)]]
vertex VertexOut vertex_displace_quad(
  patch_control_point<VertexIn> controlPoints [[stage_in]],
  constant InstanceConstants *instances [[buffer(2)]],
  constant FrameConstants &frame [[buffer(3)]],
  texture2d<float, access::sample> displacementMap [[texture(0)]],
  float2 positionInPatch [[position_in_patch]],
  uint instanceID [[instance_id]])
{
    constant InstanceConstants &instance = 
      instances[instanceID];    float3 p00 = controlPoints[0].position;
    float3 p01 = controlPoints[1].position;
    float3 p10 = controlPoints[3].position;
    float3 p11 = controlPoints[2].position;
    float3 position = bilerp(
      p00, p01, p10, p11, positionInPatch);    float3 n00 = controlPoints[0].normal;
    float3 n01 = controlPoints[1].normal;
    float3 n10 = controlPoints[3].normal;
    float3 n11 = controlPoints[2].normal;
    float3 normal = bilerp(
      n00, n01, n10, n11, positionInPatch);
      
    // … other attributes …

To determine the degree of displacement for a given vertex, we sample the displacement map at the (interpolated) texture coordinates and take just the red channel

constexpr sampler bilinearSampler(coord::normalized,
                                    filter::linear,
                                    mip_filter::none,
                                    address::repeat);
  float displacement = displacementMap.sample(
    bilinearSampler, texCoords).r;

To determine the position of the displaced vertex, we combine the interpolated original position, the sampled displacement, and the displacement factor (which we can vary interactively for demonstration purposes, or bake into the asset).

position += normal * displacement * frame.displacementFactor;

Below is an exaggerated example of displacement mapping, showing how highly subdivided geometry, combined with displacement mapping and normal mapping, produces a more realistic appearance than normal mapping alone.

With this, we have achieved our goal: implementing tessellation and displacement mapping in Metal. Next time, we will look at how to bring meshes to life with vertex skinning.